package org.example.List;

import java.beans.Transient;
import java.util.Arrays;
import java.util.concurrent.atomic.AtomicInteger;

public class ArrayList implements List{

    /**
     * 默认容量
     */
    private static final int DEFAULT_CAPACITY = 10;
  
    /**
     * 数组允许分配的最大值
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  
    /**
     * 可共享的空实例数组 capacity == 0
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
  
    /**
     * 默认数组
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  
    private static volatile   int size = 0;

//    private static volatile  int minCapacity = DEFAULT_CAPACITY;
    /**
     * 底层数据结构 数组 真正存放数据的数据结构
     */
    transient Object[] elementData;

    public ArrayList(int initialCapacity) {
        //直接初始化
        if(initialCapacity < 0){
            this.elementData = new Object[initialCapacity];
        }else if(initialCapacity == 0){
            this.elementData = EMPTY_ELEMENTDATA;
        }else{
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
    }

    public ArrayList() {
        this.elementData = EMPTY_ELEMENTDATA;
    }

    @Override
    public Object get(int index) {
        rangeCheckForAdd(index);
        return elementData[index];
    }

    @Override
    public Object set(int index, Object o) {
        rangeCheckForAdd(index);
        Object oldValue = elementData[index];
        elementData[index] = o;
        return oldValue;
    }

    @Override
    public void add(int index, Object o) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size+1);
        System.arraycopy(elementData, index, elementData, index+1, elementData.length-index);
        elementData[index] = o;
        size++;
    }

    private void rangeCheckForAdd(int index) {
        if(index >= size||index<0){
            throw new IndexOutOfBoundsException();
        }
    }

    @Override
    public boolean add(Object o) {
        ensureCapacityInternal(size+1);
        elementData[size++]=o;
        return true;
    }
    /**
     * 确保底层数组的容量是大于当前需要的最小容量
     * 如果容量不够就进行扩容
     *
     * @param minCapacity 所需最小容量
     */
    private void ensureCapacityInternal(int minCapacity) {
        if(elementData ==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
            minCapacity =Math.max(DEFAULT_CAPACITY,  minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        // 检查是否超出了数组范围，确保不会溢出
        if(minCapacity-elementData.length>0){
            grow(minCapacity);
        }
    }

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // 默认增加原有素组大小的一半
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 选择 newCapacity 和 minCapacity 中的较大者
        if(newCapacity - minCapacity < 0){
            newCapacity = minCapacity;
        }
        if(newCapacity - MAX_ARRAY_SIZE > 0){
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData,newCapacity);
    }

    private int hugeCapacity(int minCapacity) {
        if(minCapacity < 0){
            throw new OutOfMemoryError();
        }
        return (minCapacity > MAX_ARRAY_SIZE)?
                Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

    @Override
    public int indexOf(Object o) {
        if (o == null) { // 如果要查找的元素是 null
            for (int i = 0; i < size; i++) // 遍历列表
                if (elementData[i]==null) // 如果找到了 null 元素
                    return i; // 返回元素的索引
        } else { // 如果要查找的元素不是 null
            for (int i = 0; i < size; i++) // 遍历列表
                if (o.equals(elementData[i])) // 如果找到了要查找的元素
                    return i; // 返回元素的索引
        }
        return -1; // 如果找不到要查找的元素，则返回 -1
    }

    @Override
    public int lastIndexOf(Object o) {
        if (o == null) { // 如果要查找的元素是 null
            for (int i = size-1; i >= 0; i--) // 从后往前遍历列表
                if (elementData[i]==null) // 如果找到了 null 元素
                    return i; // 返回元素的索引
        } else { // 如果要查找的元素不是 null
            for (int i = size-1; i >= 0; i--) // 从后往前遍历列表
                if (o.equals(elementData[i])) // 如果找到了要查找的元素
                    return i; // 返回元素的索引
        }
        return -1; // 如果找不到要查找的元素，则返回 -1
    }

    @Override
    public boolean contains(Object o) {
       return indexOf(o)>=0?true:false;

    }

    @Override
    public Object remove(int index) {
        rangeCheckForAdd(index);
        Object oldValue = elementData[index];
        int numMoved = size -index-1;
        System.arraycopy(elementData,index+1,elementData,index,numMoved);
        //size - 1
        elementData[--size]=null;//提醒gc回收
        return oldValue;
    }

    @Override
    public boolean remove(Object o) {
        if(o==null) {
            for (int index = 0; index < size(); index++) {
                if (elementData[index] == null) { // 如果找到了 null 元素
                    fastRemove(index); // 调用 fastRemove 方法快速删除元素
                    return true; // 返回 true，表示成功删除元素
                }
            }
        }else { // 如果要删除的元素不是 null
                for (int index = 0; index < size; index++) // 遍历列表
                    if (o.equals(elementData[index])) { // 如果找到了要删除的元素
                        fastRemove(index); // 调用 fastRemove 方法快速删除元素
                        return true; // 返回 true，表示成功删除元素
                    }
            }

        return false;
    }

    private void fastRemove(int index) {
        int numMoved = size - index - 1; // 计算需要移动的元素个数
        if (numMoved > 0) // 如果需要移动元素，就用 System.arraycopy 方法实现
            System.arraycopy(elementData, index+1, elementData, index,
                    numMoved);
        elementData[--size] = null; // 将数组末尾的元素置为 null，让 GC 回收该元素占用的空间
    }

    @Override
    public int size() {
        return elementData.length;
    }

    @Override
    public boolean empty() {
        return size==0?true:false;
    }
}
